package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1514. 概率最大的路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/20 11:36
 */
public class MaxProbability {

    public static void main(String[] args) {
        MaxProbability test = new MaxProbability();

        // 0.25
//        int n = 3;
//        int[][] edges = {{0,1},{1,2},{0,2}};
//        double[]  succProb = {0.5,0.5,0.2};
//        int start = 0;
//        int end = 2;

        // 0.3
//        int n = 3;
//        int[][] edges = {{0,1},{1,2},{0,2}};
//        double[]  succProb = {0.5,0.5,0.3};
//        int start = 0;
//        int end = 2;

        // 0
        int n = 3;
        int[][] edges ={{0,1}};
        double[]  succProb = {0.5};
        int start = 0;
        int end = 2;

        double v = test.maxProbability(n, edges, succProb, start, end);
        System.out.println(v);
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

        Map<Integer, List<Integer>> map = new HashMap<>();
        Map<Integer, Double> succMap = new HashMap<>();
        for (int i = edges.length - 1; i >= 0; i--) {
            int[] edge = edges[i];
            int a = Math.min(edge[0], edge[1]);
            int b = Math.max(edge[0], edge[1]);
            map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
            map.computeIfAbsent(b, v -> new ArrayList<>()).add(a);
            succMap.put((a << 15) + b , succProb[i]);
        }

        double[] arr = new double[n];
        arr[start] = 1;

        LinkedList<Integer> list = new LinkedList<>();
        LinkedList<Integer> cache = new LinkedList<>();
        list.addLast(start);
        while (!list.isEmpty()) {
            while (!list.isEmpty()) {

                int k = list.pollFirst();
                double s = arr[k];

                List<Integer> li = map.get(k);
                if (li != null) {
                    for (int v : li) {
                        double succ = succMap.get((Math.min(v, k) << 15) + Math.max(v, k));
                        if (s * succ > arr[v]) {
                            arr[v] = s * succ;
                            if (v != end) {
                                cache.addLast(v);
                            }
                        }
                    }
                }
            }

            list.addAll(cache);
            cache.clear();
        }

        return arr[end];
    }

}
